#include "lib.h"

/*-------------------------------------------------------------------------*/
/**
  @file		pq_pairing.c
  @author	Renaud Wanschoor
  @date	july 2004
  @version	$Revision: 2.2 $
  @brief	pairing heap implementation

  Pairing heap implementation for priority queues
  \todo This implemtation is working but is not finalized for pagrid
  usage, the interface describe in plib.h must be check for consistency with this
  file
  
*/
/*--------------------------------------------------------------------------*/

/************************************************************************/

typedef struct HeapElt{
  double gain;
  struct HeapElt* p;	/* previous in list */
  struct HeapElt* n;	/* next in list */
  struct HeapElt* s;	/* next sibling */
}HeapElt;

/************************************************************************/

static void HeapMoveDown(Heap* h,HeapElt* elt);
static void HeapMoveUp(Heap* h,HeapElt* elt);
static HeapElt* HeapLink(HeapElt* elt1,HeapElt* elt2);
static HeapElt* HeapCombine(Heap*,HeapElt* elt);
#ifdef DEBUG
static void HeapPrintR(HeapElt* elt,int left);
#endif

/************************************************************************/

void   HeapInit(HeapFarm* farm, Heap* h,int size){
  h->type  = HEAP_PAIRING;
  h->farm  = farm;
  h->mem   = NULL;

  h->s     = 0;
  h->max_s = size; 
  
  h->pos   = NULL;		/* not used by pairing heap */
  h->h     = NULL;
  
  HeapFarmNeed(farm,size*sizeof(HeapElt));
}

/************************************************************************/

void HeapClean(Heap* h){
  int i;
  HeapElt* mem = h->mem;
  int     size = h->s;

  if(size <= h->max_s){
    for(i=0;i<size;i++){
      mem[i].gain = -INFINITY;
      mem[i].n    = NULL;
      mem[i].p    = NULL;
      mem[i].s    = NULL;
    }

    h->s = 0;
    h->h = NULL;  
  }else
    NOTICE((1,
	    "HeapClean error code 1 : heap not continuous cannot clean it\n")
	   );
}

/************************************************************************/

void HeapFree(Heap* h){
  h->s      = 0;
  h->max_s  = 0;
  h->h      = NULL;
  h->mem    = NULL;
  h->farm   = NULL;
}

/***********************************************************************/

int HeapInsert(Heap* h,double gain,int pos){
  static HeapElt* farm_m = NULL;
  HeapElt* heap_m = h->mem;
  int idx = h->s;
  HeapElt* elt;

  if(heap_m == NULL){
    heap_m = h->mem = HeapFarmHeapRequest(h->farm,h->max_s*sizeof(HeapElt));
    farm_m = (HeapElt*)(h->farm->start);
  }

  if(pos != -1){
    farm_m[pos].gain = gain;
    farm_m[pos].p    = NULL;
    farm_m[pos].n    = NULL;
    farm_m[pos].s    = NULL;
    h->h = HeapLink(h->h,&(farm_m[pos]));

    return pos;
  }

  h->s++;
  
  if(h->s<=h->max_s){
    heap_m[idx].gain = gain;
    heap_m[idx].p    = NULL;
    heap_m[idx].n    = NULL;
    heap_m[idx].s    = NULL;
    if(h->h == NULL)
      h->h = &(heap_m[idx]);
    else
      h->h = HeapLink(h->h,&(heap_m[idx]));
    return &(heap_m[idx]) - farm_m;
  }

  elt = HeapFarmRequest(h->farm,sizeof(HeapElt));
  elt->gain = gain;
  elt->p    = NULL;
  elt->n    = NULL;
  elt->s    = NULL;
  if(h->h == NULL)
    h->h = elt;
  else
    h->h = HeapLink(h->h,elt);
  return elt - farm_m;
}

/**********************************************************************/

void HeapUpdate(Heap* h, int epos, double gain){

  HeapElt* elt  = &(((HeapElt*)h->farm->start)[epos]);
  HeapElt* heap = h->h;
  int up = gain > elt->gain;

  elt->gain = gain;

  if(elt == heap){
    if(elt->n != NULL){
      elt->n->p = NULL;
      h->h      = elt->n; // TEMP
      heap      = HeapCombine(h,elt->n);
      elt->n    = NULL;
      h->h      = HeapLink(heap,elt);
    }
    return;
  }

  if(up)
    HeapMoveUp(h,elt);
  else
    HeapMoveDown(h,elt);
}

/**************************************************************************/

double HeapSeeHead(Heap* h){
  return ((HeapElt*)h->h)->gain;
}

/**************************************************************************/

int HeapGetHead(Heap* h){
  return (HeapElt*)h->h - (HeapElt*)h->farm->start;
}

/**************************************************************************/

void   HeapUpdateHead(Heap* h){
  HeapElt* head;

  head = &((HeapElt*)h->farm->start)[HeapRemoveHead(h)];
  head->gain *= -1;

  h->h = HeapLink(h->h,head);

}

/**************************************************************************/

int   HeapRemoveHead(Heap* h){
  HeapElt* elt  = h->h;
  HeapElt* next;
  
  if(elt == NULL)
    return -1;

  next    = elt->n;
  elt->n  = NULL;

  if(next == NULL){
    h->h = NULL;
    return elt - ((HeapElt*)h->farm->start);
  }

  next->p = NULL;
  h->h = HeapCombine(h,next);

  return elt - ((HeapElt*)h->farm->start);
}

/**************************************************************************/

double HeapGetGain(Heap* h,int epos){
  return ((HeapElt*)h->farm->start)[epos].gain;
}

/**************************************************************************/

void HeapMoveDown(Heap* h,HeapElt* elt){
  HeapElt* next = NULL;

  if(elt->n != NULL && elt->n->gain > elt->gain){
    /* combine */
    next       = HeapCombine(h,elt->n);
    elt->n     = NULL;
    
    /* link previous */
    next->p    = elt->p;
    if(elt->p->n == elt)
      next->p->n = next;
    else
      next->p->s = next;

    /* link others */
    elt->p = next;
    if((next->s = elt->s) != NULL)
      next->s->p = next;
    if((elt->s = next->n) != NULL)
      elt->s->p = elt;
    next->n = elt;
  }
}

void HeapMoveUp(Heap* h, HeapElt* elt){

  if(elt->p->n == elt && elt->p->gain > elt->gain)
    return;

  if(elt->s != NULL)
    elt->s->p = elt->p;
  if(elt->p->n == elt)
    elt->p->n = elt->s;
  else
    elt->p->s = elt->s;
  
  elt->s = NULL;
  h->h = HeapLink(h->h,elt);
}

HeapElt* HeapLink(HeapElt* elt1,HeapElt* elt2){
  
  if(elt2 == NULL)
    return elt1;
  
  /* attach elt2 to child of elt1 */
  if(elt1->gain > elt2->gain){
    elt2->p = elt1;
    if((elt1->s = elt2->s) != NULL)
      elt1->s->p = elt1;
    if((elt2->s = elt1->n) != NULL)
      elt2->s->p = elt2;
    elt1->n = elt2;

    return elt1;
  }
  
  /* attach elt1 to child of elt2 */
  if((elt2->p = elt1->p) != NULL){
    if(elt1->p->n == elt1)
      elt2->p->n = elt2;
    else
      elt2->p->s = elt2;
  }
  elt1->p = elt2;
  if((elt1->s = elt2->n) != NULL)
    elt1->s->p = elt1;
  elt2->n = elt1;
  
  return elt2;
}

HeapElt* HeapCombine(Heap* h,HeapElt* elt){
  if(elt->s == NULL)
    return elt;

  while(elt->s != NULL){

    elt = HeapLink(elt,elt->s);

    if(elt->s != NULL)
      elt = elt->s;      
  }
  
  while(elt->p != NULL && elt->p->n != elt)
    elt = HeapLink(elt->p,elt);

  return elt;
}

/**************************************************************************/
/****************************** DEBUGGING *********************************/
/**************************************************************************/

#ifdef DEBUG
double HeapGain(Heap* h, int idx){
  return ((HeapElt*)h->farm->start)[idx].gain;
}

void HeapPrint(Heap* h){
  HeapElt* elt = h->h;

  if(elt == NULL)
    return;

  printf("heap:\n");
  printf("%10.2f\n",elt->gain);
  if(elt->n != NULL){
    ERROR((elt->n->p!=elt,"break link 1\n"));
    HeapPrintR(elt->n,0);
  }
}
void HeapPrintR(HeapElt* elt,int left){
  int i;
  HeapElt* sib = NULL;

  for(i=0;i<left;i++)printf("%11s","");

  printf("%10.2f ",elt->gain);left++;
  
  sib = elt;
  while(sib->s != NULL){
    ERROR((sib->s->p != sib,"break link 2\n"));
    sib = sib->s; 
    printf("%10.2f ",sib->gain);
    left++;
  }
  printf("\n");left--;
  while(sib->p->n != sib){
    if(sib->n != NULL){
      NOTICE((sib->n->p != sib,"break link 3\n"));
      HeapPrintR(sib->n,left);
    }
    left--;
    ERROR((sib->p->s != sib,"break link 4\n"));
    sib = sib->p;
  }

  if(elt->n != NULL){
    ERROR((elt->n->p != elt,"break link 5\n"));
    HeapPrintR(elt->n,left);
  }
}
#endif
